package linearlist;


import org.junit.Test;

import java.util.*;

/**
 * @author zhm
 * @date 2020/9/10
 */
public class ListNodeOperation {

    /**
     * 反转链表
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {

        //如果单链表为空或者只有一个数组，直接返回
        if(head==null || head.next==null){
            return head;
        }

        //最新的首节点
        ListNode headTemp = head;

        while (head.next!=null){
            ListNode temp = head.next;
            head.next = head.next.next;
            temp.next = headTemp;
            headTemp = temp;
        }
        head = headTemp;
        return head;
    }

    /**
     * 删除链表中的所有匹配值
     * @param head
     * @param val
     * @return
     */
    public ListNode removeElements(ListNode head, int val) {

        while (head!=null && head.val == val){
            head = head.next;
        }
        if(head==null){
            return head;
        }
        //确定真正的首节点
        ListNode temp = head;
        while (temp.next!=null){
            if(temp.next.val==val){
                temp.next = temp.next.next;
            }else {
                temp = temp.next;
            }
        }
        return head;
    }

    /**
     * 判断链表中是否有环
     * @param head
     * @return
     */
    public boolean hasCycle(ListNode head) {
        if(head==null){
            return false;
        }
        //快指针
        ListNode fastPointer = head;
        //慢指针
        ListNode slowPointer = head;
        while (fastPointer.next!=null){
            fastPointer = fastPointer.next.next;
            slowPointer = slowPointer.next;
            if (fastPointer==null){
                return false;
            }
            if(fastPointer==slowPointer){
                return true;
            }
        }
        return false;
    }

    /**
     * 判断链表是否有环，返回链表开始入环的第一个节点
     * HashSet 方式
     * @param head
     * @return
     */
    public ListNode detectCycle(ListNode head) {
        Set<ListNode> listNodeSet = new HashSet<>();
        ListNode temp = head;
        while (temp!=null){
            if(listNodeSet.contains(temp)) {
                return temp;
            }else {
                listNodeSet.add(temp);
                temp = temp.next;
            }
        }
        return null;
    }

    /**
     * 优雅解决方式
     * @param head
     * @return
     */
    public ListNode detectCycle2(ListNode head) {

        if(head==null){
            return null;
        }
        ListNode firstMeetPointer = this.getFirstMeetPointer(head);
        if(firstMeetPointer==null){
            return null;
        }
        ListNode temp = head;
        while (temp!=firstMeetPointer){
            temp = temp.next;
            firstMeetPointer = firstMeetPointer.next;
        }

        return temp;
    }

    /**
     * 获取链表快慢指针的相遇点
     * @param head
     * @return
     */
    private ListNode getFirstMeetPointer(ListNode head){
        //先找到第一次相遇的节点位置
        ListNode fastPointer = head;
        ListNode slowPointer = head;
        while (fastPointer.next!=null){
            fastPointer = fastPointer.next.next;
            slowPointer = slowPointer.next;
            if(fastPointer==null){
                return null;
            }
            if(fastPointer==slowPointer){
                return fastPointer;
            }
        }
        return null;
    }


    /**
     * 删除链表的倒数第N个节点（HashMap 方式，不够优雅，浪费空间多）
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {

        ListNode temp = head;

        Map<Integer,ListNode> map = new HashMap<>();
        int pos = 0;
        while (temp!=null){
            map.put(pos,temp);
            temp = temp.next;
            pos++;
        }
        if(n==map.size()){
            head = head.next;
        }else {
            ListNode listNode = map.get(map.size() - (n + 1));
            listNode.next = listNode.next.next;
        }
        return head;
    }

    /**
     * 删除链表的倒数第N个节点,增加哑节点简化操作（不用判断头指针为空的情况）
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd2(ListNode head, int n) {

        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode dummyTemp1 = dummy;
        ListNode dummyTemp2 = dummy;

        for (int i = 0; i < n; i++) {
            dummyTemp1 = dummyTemp1.next;
        }
        while (dummyTemp1.next!=null){
            dummyTemp2 = dummyTemp2.next;
            dummyTemp1 = dummyTemp1.next;
        }

        dummyTemp2.next = dummyTemp2.next.next;
        return dummy.next ;
    }

    /**
     * 找到两个单链表相交的起始节点(不够优雅，浪费空间多)
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode tempA = headA;
        ListNode tempB = headB;
        Set<ListNode> set = new HashSet<>();
        while (tempA!=null || tempB!=null){
            if(tempA!=null){
                if(set.contains(tempA)){
                    return tempA;
                }
                set.add(tempA);
                tempA = tempA.next;
            }
            if(tempB!=null){
                if(set.contains(tempB)){
                    return tempB;
                }
                set.add(tempB);
                tempB = tempB.next;
            }
        }
        return null;
    }

    /**
     * 找到两个单链表相交的起始节点
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        if(headA==null || headB==null){
            return null;
        }
        ListNode tempA = headA;
        ListNode tempB = headB;
        while (tempA!=tempB){
           tempA = tempA==null?headB:tempA.next;
           tempB = tempB==null?headA:tempB.next;
        }
        return tempA;
    }

        /**
         * 奇偶链表
         * @param head
         * @return
         */
    public ListNode oddEvenList(ListNode head) {
        if(head==null || head.next==null){
            return head;
        }
        ListNode odd = head;
        ListNode even = head.next;
        ListNode evenHead = head.next;
        while (even!=null && even.next!=null){
            odd.next = even.next;
            odd = odd.next;
            even.next = odd.next;
            even = even.next;
        }
        odd.next = evenHead;

        return head;
    }

    /**
     * 回文链表
     * @param head
     * @return
     */
    public boolean isPalindrome(ListNode head) {
        ListNode fastPointer = head;
        ListNode slowPointer = head;

        while (fastPointer!=null && fastPointer.next!=null){
            fastPointer = fastPointer.next.next;
            slowPointer = slowPointer.next;
        }



        return false;
    }

    public ListNode findMedianListNode(ListNode head){
        ListNode fastPointer = head;
        ListNode slowPointer = head;
        while (fastPointer!=null && fastPointer.next!=null){
            fastPointer = fastPointer.next.next;
            slowPointer = slowPointer.next;
        }
        return slowPointer;
    }

    /**
     * 合并两个有序链表
     * @param l1
     * @param l2
     * @return
     */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

        ListNode dummy = new ListNode(0);
        ListNode dummyTemp = dummy;
        ListNode temp1 = l1;
        ListNode temp2 = l2;
        while (temp1!=null || temp2!=null){
            if(temp1==null){
                dummyTemp.next = new ListNode(temp2.val);
                temp2 = temp2.next;
            }else if(temp2==null){
                dummyTemp.next =  new ListNode(temp1.val);
                temp1 = temp1.next;
            }else {
                if(temp1.val<temp2.val){
                    dummyTemp.next = new ListNode(temp1.val);
                    temp1 = temp1.next;
                }else {
                    dummyTemp.next = new ListNode(temp2.val);
                    temp2 = temp2.next;
                }
            }
            dummyTemp = dummyTemp.next;
        }

        return dummy.next;
    }

    /**
     * 不够优雅（复杂度为 N*N ）
     * 排序链表
     * @param head
     * @return
     */
    public ListNode sortList(ListNode head) {
        if(head==null || head.next==null){
            return head;
        }
        //哑结点,用来简化操作，不实际返回数据
        ListNode dummy = new ListNode(-1,head);
        ListNode dummyTemp = dummy;

        //从第二个节点开始处理
        ListNode temp = head.next;
        //定义当前节点前节点
        ListNode tempPre = head;
        while (temp!=null){
            //需要交换的情况
            if(temp.val<tempPre.val){
                while (dummyTemp.next!=null){
                    if(dummyTemp.next.val>temp.val){
                        tempPre.next = temp.next;
                        temp.next = dummyTemp.next;
                        dummyTemp.next = temp;
                        dummyTemp = dummy;
                        temp =  tempPre.next;
                        break;
                    }else {
                        dummyTemp = dummyTemp.next;
                    }
                }
            }else {
                //不需要交换的情况
                tempPre = tempPre.next;
                temp = temp.next;
            }
        }

        return dummy.next;
    }

    /**
     * 两个非空链表相加并且不改变两个链表
     * @param l1
     * @param l2
     * @return
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        ListNode temp1 = l1;
        ListNode temp2 = l2;
        Stack<Integer> s1 = new Stack<>();
        Stack<Integer> s2 = new Stack<>();

        while (temp1!=null){
            s1.push(temp1.val);
            temp1 = temp1.next;
        }
        while (temp2!=null){
            s2.push(temp2.val);
            temp2 = temp2.next;
        }
        int carry = 0;
        ListNode ans = null;
        while (!s1.empty() || !s2.empty() || carry>0){
            int a = s1.isEmpty() ? 0 : s1.pop();
            int b = s2.isEmpty() ? 0 : s2.pop();
            int cur = a + b + carry;
            carry = cur / 10;
            cur %= 10;
            ListNode curNode = new ListNode(cur);
            curNode.next = ans;
            ans = curNode;
        }
        return ans;
    }
}